package demo.practice.binary_search;

import java.util.PriorityQueue;

class KV{

    public int index;
    public int val;

    public KV(int index,int val){
        this.index=index;
        this.val=val;
    }
}

public class P1337 {

    /*
    * mat =
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]],
    * */


    public static void main(String[] args) {
       P1337 p1337= new P1337();
        int[] ints = p1337.kWeakestRows(new int[][]{{1, 1, 0, 0, 0}, {1, 1, 1, 1, 0}, {1, 0, 0, 0, 0}, {1, 1, 0, 0, 0}, {1, 1, 1, 1, 1}}, 3);
        System.out.println(ints);
    }



    public int[] kWeakestRows(int[][] mat, int k) {
        PriorityQueue<KV> queue= new PriorityQueue<KV>((i,j)->{
            if(j.val!=i.val)
                return  j.val-i.val;
            else
                return  j.index-i.index;
        });
        int[]  weaks=new int[k];

        for(int i=0;i<mat.length;i++){
            queue.add(new KV(i,getWeakes(mat[i])));
            if(queue.size()>k)
                queue.poll();
        }

        for(int i=weaks.length-1;i>=0;i--){
            weaks[i]=queue.poll().index;
        }

        return weaks;
    }

    private int getWeakes(int[] row){
            if(row.length==0)
                return 0;
            int min=0;
            int max=row.length-1;

            while (min<=max){
                //找到第一个为0的索引，索引的值即为 个数 比如  [1,1,0,0,0]  第一个为0的索引为1
                int mid= min+(max-min)/2;
                if(row[mid]==0 ){
                    //这种情况，第一个0在前面，或者为当前值
                    max=mid;
                    if(mid==min)
                        break;
                }else{
                    min=mid+1;//有可能所有的数都为1,则最终min=？ mid=(row.length-1)+1 ，也就是length 个
                }
            }
            return min;
    }
}
